
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "stdafx.h"
#include "time.h"
#include <float.h>
#include <fstream>

#include <iostream>
#include <cstdlib>
#include <sys/stat.h>

#include <stdio.h>
#include <sstream>

#include <cmath> //for llroundl

using namespace std;

struct DescID{
	int id;
	signed char dim[1024];
};

struct leaderInfo {
	FILE* file;
	string fileName;
	int id;
	DescID descriptor;
	DescID* page;
	int descCount;
	int totalDescs;
	long long int* centroidData;
	signed char* actualCentroid;

};

int maxOpenFiles = 100;
int firstFile = 0;
int leaderFileCount = 0;
int* leaderFiles = new int[maxOpenFiles];

leaderInfo* leaders;

void WriteDescs(DescID *descs, int descCount, int bytesPerDesc, FILE *outfile)
{
	for (int i=0; i<descCount; i++)
		fwrite((char*)&descs[i], bytesPerDesc, 1, outfile);
}

void FillPage(int padBytes, FILE *outFile)
{
	char *sp = new char('\0');
	/*char sp = new char[(padBytes/8)];
	for (int x=0; x<(padBytes/8); x++)
		sp[x] = '\0';
	*/
	fwrite((char *)sp, sizeof(char), padBytes, outFile);
	delete sp;
}

void WriteCluster(int pageOffset, int pages, int size, signed char *centroid, int numdims, FILE *outfile, int id)
{
	fwrite((char *)&pageOffset, sizeof(int), 1, outfile);
	fwrite((char *)&pages,      sizeof(int), 1, outfile);
	fwrite((char *)&size,       sizeof(int), 1, outfile);
	fwrite((char *)&id,         sizeof(int), 1, outfile);
	fwrite((char *)centroid,   1,     numdims, outfile);
}

float Distance(signed char* A, signed char* B, int numDims, float curMinDist) {
	// This is the algorithm of Figure 5 of the TR
	float dist = 0.0;
	/* * /
	 for (int i=0; i<numDims; i++) {
	 float dimdist = (A[i] - B[i]);
	 dist += dimdist * dimdist;

	 if (dist > curMinDist) return FLT_MAX;
	 }
	 return dist;
	 //*/
	/* */
	int i = 0;
	int n = (numDims + 7) / 8;
	int n0=0, n1=0, n2=0,n3=0,n4=0,n5=0,n6=0,n7=0;
    switch (numDims % 8) {
			case 0: do { n0 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 7:      n1 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 6:      n2 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 5:      n3 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 4:      n4 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 3:      n5 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 2:      n6 = (A[i] - B[i]) * (A[i] - B[i++]);
			case 1:      n7 = (A[i] - B[i]) * (A[i] - B[i++]);
				dist += ((n0 + n1)+((n2+n3)+((n4+n5)+(n6+n7))));
		} while (--n && (dist < curMinDist));
    }
	return dist;
	// */
};

void OpenLeaderFile(int leaderId) {
	// Ef skr· er ˛egar opin, ekki gera neitt
	int count = (leaderFileCount == maxOpenFiles ? maxOpenFiles : leaderFileCount);
	for (int i = 0; i < count; i++) {
		if (leaderFiles[i] == leaderId) return;
	}

	// EF ˛a er ekki b˙i a fylla Ì arrayi af skr·m
	if (leaderFileCount < maxOpenFiles) {
		// Setja ˛a Ì nÊsta opna slot
		leaderFiles[leaderFileCount] = leaderId;
		// opna skr·nna
		leaders[leaderId].file = fopen(leaders[leaderId].fileName.c_str(), "ab");
		// og hÊkka tˆluna
		leaderFileCount++;
	} else {
		// Annars ˛arf a loka fyrstu skr·nni,
		// opna n˝ju ˛ar sem h˙n var, og
		// hÊkka teljara um einn
		fclose( leaders[ leaderFiles[firstFile] ].file );

		leaderFiles[firstFile] = leaderId;
		leaders[leaderId].file = fopen(leaders[leaderId].fileName.c_str(), "ab");

		firstFile++;
		if(firstFile == maxOpenFiles) firstFile = 0;
	}
}

int main(int argc, char *argv[])
{
    if (!(argc >= 4 && argc <= 6)) {
		cout << "Usage: partition <in-file> <dims> <out-file> <cl-size> <im-count> {<ordering>}" << endl;
		cout << "           note: partitions a descriptor file uniformly into 'clusters'" << endl;
		cout << "         <in-file> is a binary file containing (id, descriptor) pairs" << endl;
		cout << "           note: id = int, each dimension = byte, ordering is irrelevant" << endl;
        cout << "         <dims> is the dimensionality of the descriptors" << endl;
        cout << "         <out-file> is the stem of a name for the three output files" << endl;
		cout << "           note: suffixes will be .cnfg, .indx, and .data" << endl;
        cout << "         (optional) <im-count> is the number of images (filters image ids >= im-count)" << endl;
        cout << "         (optional) <ordering> indicates that the file is ordered by image ids" << endl;
		exit(2);
	}

	// Find the page size
	size_t pagesize = 4096;
	cout << "Page size: " << pagesize << endl;

	// Get the number of dimensions
	size_t numdims = atoi(argv[2]);
	cout << "Dimensions: " << numdims << endl;

	// Read max image count and ordering
	int maxImageCount = argc == 4 ? 0 : atoi(argv[4]);
	int ordering = (argc == 6);
	if (ordering)
		cout << "Ordering: Yes" << endl;
	else
		cout << "Ordering: No" << endl;

	// Create the output file names
	string stemFilename = argv[3];
	string cnfgFilename = stemFilename;
	cnfgFilename.append(".cnfg");
	cout << "Config file: " << cnfgFilename.c_str() << endl;
	string indxFilename = stemFilename;
	indxFilename.append(".indx");
	cout << "Index file: " << indxFilename.c_str() << endl;
	string dataFilename = stemFilename;
	dataFilename.append(".data");
	cout << "Data file: " << dataFilename.c_str() << endl;

	// Open the config and index files
	FILE *cnfgFile = fopen(cnfgFilename.c_str(), "wb");
	FILE *indxFile = fopen(indxFilename.c_str(), "wb");


	// Calculate structural information about pages
	size_t descSizeBytes = numdims + 4; //sizeof(int); // descSizeBytes is the size of each descriptor
	int descsPerPage = pagesize / descSizeBytes; // descsPerPage is how many descriptors can get on any page
	size_t descBytesPerPage = descSizeBytes * descsPerPage; // descBytesPerPage is how many bytes descriptors occupy on each page

	// Open up the infile and check the size
	FILE* infile = fopen(argv[1], "rb");
	struct stat filestat;
	fstat(fileno(infile), &filestat);
	off_t byteCount = filestat.st_size;
	long long int totalDescs = byteCount / descSizeBytes;
	cout << "Total descriptors in infile: " << totalDescs << endl;

	// Find out how many leaders we are going to find
	int leaderCount = sqrtl(totalDescs);
	cout << "Leaders to find: " << leaderCount << endl;

	if ((byteCount % descSizeBytes) != 0)
	{
		cout << "WARNING: Input descriptor file not exact multiple of descriptor size in bytes:" << endl;
		cout << "\tDesc size: " << descSizeBytes <<" || Bytes in file: " << byteCount << endl;
		cout << "\tExcess bytes: " << (byteCount % descSizeBytes) << "\tExcess bytes will be ignored." << endl;
	}

	time_t startTime = time(NULL);
	time_t chapterTime = time(NULL);

	cout << "Choosing leaders...  " << flush;

	// The list that hold all the leaders id's
	leaders = new leaderInfo[leaderCount];

	for (int i = 0; i < leaderCount; i++) {
		bool success = true;
		int candidate = 0;
		DescID tempDesc;

		leaderInfo leader;

		do {
			// Choose a random candidate
			candidate = rand() % totalDescs;
			success = true;

			// load the candidate
			int bytePos = candidate * descSizeBytes;
			fseek(infile, bytePos, SEEK_SET);
			fread(&leader.descriptor, descSizeBytes, 1, infile);
			// If the image is out of range, don't use it and find another candidate
			if (leader.descriptor.id >= maxImageCount && maxImageCount != 0) {
				success = false;
			} else {
				// else, try to find out if the candidate has been elected before
				for (int j = 0; j < i; j++) {
					if (candidate == leaders[j].id) {
						// If he has, find another candidate.
						success = false;
						break;
					}
				}
			}
		} while (!success);

		// we found a leader, joy

		// set the info
		leader.id = candidate;
		leader.descCount = 0;
		leader.totalDescs = 0;
		leader.page = new DescID[descsPerPage];
		leader.centroidData = new long long int[numdims];
		leader.actualCentroid = new signed char[numdims];
		for (int j = 0; j < numdims; j++) {
			leader.centroidData[j] = 0;
			leader.actualCentroid[j] = 0;
		}

		// Put the leader as the first descriptor
		leader.page[0] = leader.descriptor;
		leader.totalDescs++;
		leader.descCount++;

		// Make the file name
		std::stringstream out;
		out << "leaders/" << i;
		leader.fileName = out.str();

		leaders[i] = leader;
	}

	// Rewind
	fseek(infile, 0, SEEK_SET);

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;
	chapterTime = time(NULL);

	cout << "Clustering descriptors to temporary leader files, please wait...  " << flush;


	// Go through all the descriptors and put them in the nearest leader's file
	int imageCount = 0;
	DescID descriptor;
	while (!feof(infile)) {
		if (fread(&descriptor, descSizeBytes, 1, infile) == 1) {

			// We have a descriptor, check whether image id is in range
			if (descriptor.id < maxImageCount || maxImageCount == 0) {
				// This descriptor is a keeper
			} else if (ordering) {
				// If the file is ordered, then we are finished reading
				break;
			} else {
				// try next one
				continue;
			}

			// Find the nearest leader
			float minDist = FLT_MAX;
			int leaderId = 0;
			for ( int i = 0; i < leaderCount; i++) {
				float dist = Distance(descriptor.dim, leaders[i].descriptor.dim, 72, minDist);
				if (dist < minDist) {
					minDist = dist;
					leaderId = i;
				}
			}


			if(descriptor.id < 0)
				cout << descriptor.id << endl;
			if (descriptor.id > imageCount){
				imageCount = descriptor.id;
				if(imageCount < 0)
					cout << imageCount << endl;
			}

			// Keep track of the centroid for the centroid medioid calculation
			for (int j=0; j < numdims; j++)
				leaders[leaderId].centroidData[j] += descriptor.dim[j];


			// Put the descriptor into the leaders in-memory page
			leaders[leaderId].page[leaders[leaderId].descCount] = descriptor;

			leaders[leaderId].totalDescs++;
			leaders[leaderId].descCount++;
			// If page is full, write it to disk
			if ( leaders[leaderId].descCount == descsPerPage) {
				OpenLeaderFile(leaderId);
				WriteDescs( leaders[leaderId].page, descsPerPage, descSizeBytes, leaders[leaderId].file);
				leaders[leaderId].descCount = 0;
			}

		}
	}

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;
	chapterTime = time(NULL);

	cout << "Writing in-memory incomplete pages to disk...  " << flush;

	// Finish writing all the leaders pages to disk
	for ( int i = 0; i < leaderCount; i++) {
		OpenLeaderFile(i);

		if (leaders[i].descCount != 0) {
			// If the leader has some descs in the in-memory page, write them to disk
			WriteDescs( leaders[i].page, leaders[i].descCount, descSizeBytes, leaders[i].file);
		}

		// Now figure how much padding is needed to fill the last page
		int leaderPadBytes = pagesize - ( leaders[i].totalDescs*descSizeBytes % pagesize );
		if (leaderPadBytes && leaderPadBytes != pagesize) FillPage(leaderPadBytes, leaders[i].file);

		// Calculate the medioid
		float total = 0.0;
		for (int j=0; j < numdims; j++) {
			leaders[i].actualCentroid[j] = leaders[i].centroidData[j] / leaders[i].totalDescs;
		}
	}

	// Close all the leader files that are open
	int count = (leaderFileCount == maxOpenFiles ? maxOpenFiles : leaderFileCount);
	for (int i = 0; i < count; i++) {
		fclose(leaders[ leaderFiles[i] ].file);
	}
	delete[] leaderFiles;

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;
	chapterTime = time(NULL);

	cout << "Merging temporary files into data file...  " << flush;

	// Go through all the leader files and merge them

	// Create the data file
	ofstream dataFileStream(dataFilename.c_str(), fstream::trunc|fstream::binary);

	for (int i = 0; i < leaderCount; i++) {
		// open the leader file
		ifstream leaderFileStream(leaders[i].fileName.c_str(), fstream::binary);
		// write the leader file to the data file.. simple
		dataFileStream << leaderFileStream.rdbuf();
		leaderFileStream.close();
	}

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;
	chapterTime = time(NULL);

	cout << "Deleting temporary files...  " << flush;

	// Delete all the temporary leader files
	for (int i = 0; i < leaderCount; i++) {
		remove(leaders[i].fileName.c_str());
	}
	dataFileStream.close();

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;
	chapterTime = time(NULL);

	cout << "Writing cluster infos...  " << flush;


	// Write the cluster info
	int pageOffset = 0;
	for (int i = 0; i < leaderCount; i++) {
		int clusterPageCount = ceil( (float)(leaders[i].totalDescs * descSizeBytes) / pagesize );
		WriteCluster(pageOffset, clusterPageCount, leaders[i].totalDescs,
					 leaders[i].descriptor.dim, numdims, indxFile, i);

		pageOffset += clusterPageCount;

		delete[] leaders[i].page;
		delete[] leaders[i].centroidData;
		delete[] leaders[i].actualCentroid;
	}

	fclose(indxFile);

	delete[] leaders;

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;
	chapterTime = time(NULL);

	cout << "Writing the config file...  " << flush;

	// Finish the processing by writing the config file
	string cnfgout;
	char  *cnfgtmp = new char[300];

	cnfgout = "type: byte\n";
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	sprintf(cnfgtmp, "dims: %i\n", numdims);
	cnfgout = cnfgtmp;
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	sprintf(cnfgtmp, "clst: %i\n", leaderCount);
	cnfgout = cnfgtmp;
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	sprintf(cnfgtmp, "indx: %s\n", indxFilename.c_str());
	cnfgout = cnfgtmp;
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	sprintf(cnfgtmp, "data: %s\n", dataFilename.c_str());
	cnfgout = cnfgtmp;
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	sprintf(cnfgtmp, "page: %i\n", pagesize);
	cnfgout = cnfgtmp;
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	sprintf(cnfgtmp, "imgs: %i\n", imageCount+1);
	cnfgout = cnfgtmp;
	fwrite(cnfgout.c_str(), cnfgout.length(), 1, cnfgFile);

	fclose(cnfgFile);
	delete[] cnfgtmp;

	cout << "[done] (" << (time(NULL) - chapterTime) << " seconds)" << endl;

	cout << "Clustering took " << (time(NULL) - startTime) << " seconds." << endl;

	// All done!!!
	return EXIT_SUCCESS;
}
